<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="PzTbJ" id="PzTbJ"><span data-lake-id="u548d7e30" id="u548d7e30">典型回答</span></h1>
  <p data-lake-id="u85597bc7" id="u85597bc7"><span data-lake-id="uc0ab6744" id="uc0ab6744">ZSet（也称为Sorted Set）是Redis中的一种特殊的数据结构，它内部维护了一个有序的字典，这个字典的元素中既包括了一个成员（member），也包括了一个double类型的分值(score)。这个结构可以帮助用户实现记分类型的排行榜数据，比如游戏分数排行榜，网站流行度排行等。</span></p>
  <p data-lake-id="ufe97a552" id="ufe97a552"><span data-lake-id="u78b7f4be" id="u78b7f4be">​</span><br></p>
  <p data-lake-id="ubc192a1e" id="ubc192a1e"><strong><span data-lake-id="uf0d10526" id="uf0d10526">Redis中的ZSet在实现中，有多种结构，大类的话有两种，分别是ziplist(压缩列表)和skiplist(跳跃表)，但是这只是以前，在Redis 5.0中新增了一个listpack（紧凑列表）的数据结构，这种数据结构就是为了替代ziplist的，而在之后Redis 7.0的发布中，在Zset的实现中，已经彻底不在使用zipList了。</span></strong></p>
  <p data-lake-id="u1979236b" id="u1979236b"><strong><span data-lake-id="ube82c9ae" id="ube82c9ae">​</span></strong><br></p>
  <p data-lake-id="u85b7a021" id="u85b7a021"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1683438825430-ef670c73-c5f0-4a91-9795-34a9dd5e1420.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_42%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u472a2930" id="u472a2930"><strong><span data-lake-id="u9068bda1" id="u9068bda1">​</span></strong><br></p>
  <p data-lake-id="u279cc077" id="u279cc077"><span data-lake-id="u8361d571" id="u8361d571">当ZSet的元素数量比较少时，Redis会采用ZipList（ListPack）来存储ZSet的数据。ZipList（ListPack）是一种紧凑的列表结构，它通过连续存储元素来节约内存空间。当ZSet的元素数量增多时，Redis会自动将ZipList（ListPack）转换为SkipList，以保持元素的有序性和支持范围查询操作。</span></p>
  <p data-lake-id="u79784b91" id="u79784b91"><span data-lake-id="u83b36432" id="u83b36432">​</span><br></p>
  <p data-lake-id="u5509cf6a" id="u5509cf6a"><span data-lake-id="u83ee45ed" id="u83ee45ed">在这个过程中，Redis会遍历ZipList（ListPack）中的所有元素，按照元素的分数值依次将它们插入到SkipList中，这样就可以保持元素的有序性。</span></p>
  <p data-lake-id="ufabc9379" id="ufabc9379"><strong><span data-lake-id="ucbb82490" id="ucbb82490">​</span></strong><br></p>
  <p data-lake-id="ubb22f8a5" id="ubb22f8a5"><strong><span data-lake-id="u17ef16e1" id="u17ef16e1">在Redis的ZSET具体实现中，SkipList的这种实现，不仅用到了跳表，还会用到dict（字典）</span></strong></p>
  <p data-lake-id="ubd341ab8" id="ubd341ab8"><strong><span data-lake-id="u20b7169e" id="u20b7169e">​</span></strong><br></p>
  <p data-lake-id="u3d43262d" id="u3d43262d"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1683438896470-378a453b-191d-42e3-ac97-e26b3fd6daa9.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_48%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="uf40d403f" id="uf40d403f"><strong><span data-lake-id="u596d5e5b" id="u596d5e5b">​</span></strong><br></p>
  <p data-lake-id="u6bf45184" id="u6bf45184"><span data-lake-id="u129cdf40" id="u129cdf40">其中，SkipList用来实现有序集合，其中每个元素按照其分值大小在跳表中进行排序。跳表的插入、删除和查找操作的时间复杂度都是 O(log n)，可以保证较好的性能。</span></p>
  <p data-lake-id="u260e610b" id="u260e610b"><span data-lake-id="ude50fef2" id="ude50fef2">​</span><br></p>
  <p data-lake-id="ua394d112" id="ua394d112"><span data-lake-id="u773c87ff" id="u773c87ff">dict用来实现元素到分值的映射关系，其中元素作为键，分值作为值。哈希表的插入、删除和查找操作的时间复杂度都是 O(1)，具有非常高的性能。</span></p>
  <p data-lake-id="u4f26dfc9" id="u4f26dfc9"><span data-lake-id="u1b8cbeea" id="u1b8cbeea">​</span><br></p>
  <p data-lake-id="u54192b54" id="u54192b54"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1683440190031-b12ca284-ef28-4862-a995-76081de09ad6.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_29%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ua7117f7e" id="ua7117f7e"><strong><span data-lake-id="u42745d66" id="u42745d66">​</span></strong><br></p>
  <h1 data-lake-id="Ifx8q" id="Ifx8q"><span data-lake-id="u37304ac4" id="u37304ac4">扩展知识</span></h1>
  <p data-lake-id="ue73eca20" id="ue73eca20"><br></p>
  <h2 data-lake-id="dpTrH" id="dpTrH"><span data-lake-id="u87ebba78" id="u87ebba78">何时转换</span></h2>
  <p data-lake-id="u88237df1" id="u88237df1"><strong><span data-lake-id="u0bc04adf" id="u0bc04adf">​</span></strong><br></p>
  <p data-lake-id="u739e5b20" id="u739e5b20"><span data-lake-id="u63b05b53" id="u63b05b53">ZipList（ListPack）和SkipList之间是什么时候进行转换的呢？</span></p>
  <p data-lake-id="ufc3c121b" id="ufc3c121b"><span data-lake-id="u1cb1e293" id="u1cb1e293">​</span><br></p>
  <p data-lake-id="u8ede0135" id="u8ede0135"><span data-lake-id="udf01049d" id="udf01049d"><br>
    在 Redis 中，ZSET在特定条件下会使用 ziplist作为其内部表示。这通常发生在有序集合较小的时候，具体条件如下：</span></p>
  <p data-lake-id="uc4c377a9" id="uc4c377a9"><span data-lake-id="u824d1847" id="u824d1847">​</span><br></p>
  <ol list="u5943584c">
   <li fid="ue99670dd" data-lake-id="uee37e1a0" id="uee37e1a0" data-lake-index-type="true"><span data-lake-id="uf8d5972d" id="uf8d5972d">元素数量少：集合中的元素数量必须小于某个阈值（zset-max-ziplist-entries）。</span></li>
   <li fid="ue99670dd" data-lake-id="u168bb13b" id="u168bb13b" data-lake-index-type="true"><span data-lake-id="u3558583f" id="u3558583f">元素大小小：集合中的每个元素（包括值和分数）的大小必须小于指定的最大值（zset-max-ziplist-value）。</span></li>
  </ol>
  <p data-lake-id="ue8fe5145" id="ue8fe5145"><span data-lake-id="u6392eb15" id="u6392eb15">​</span><br></p>
  <p data-lake-id="ueb2183cb" id="ueb2183cb"><span data-lake-id="u593a7d05" id="u593a7d05">默认情况下，zset-max-ziplist-entries是128，zset-max-ziplist-value是64。</span></p>
  <p data-lake-id="u58e4e8e6" id="u58e4e8e6"><strong><span data-lake-id="uc1aacef0" id="uc1aacef0">​</span></strong><br></p>
  <p data-lake-id="u5236f620" id="u5236f620"><strong><span data-lake-id="u36f0e21b" id="u36f0e21b">总的来说就是，当元素数量少于128，每个元素的长度都小于64字节的时候，使用ZipList（ListPack），否则，使用SkipList！</span></strong></p>
  <p data-lake-id="u25f984a7" id="u25f984a7"><br></p>
  <h2 data-lake-id="eXNg9" id="eXNg9"><span data-lake-id="u4a048689" id="u4a048689">跳表</span></h2>
  <p data-lake-id="u42607295" id="u42607295"><br></p>
  <p data-lake-id="ua3103390" id="ua3103390"><span data-lake-id="u74b5e112" id="u74b5e112" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">跳表也是一个有序链表，如下面这个数据结构：</span></p>
  <p data-lake-id="u7f03566a" id="u7f03566a"><span data-lake-id="u8078523b" id="u8078523b" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u5ead8b78" id="u5ead8b78"><img src="https://cdn.nlark.com/yuque/0/2022/png/5378072/1671868102611-a17cd7ab-cc42-445a-b7cf-001a14ab979b.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_38%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u76142023" id="u76142023"><span data-lake-id="uf3fd87b6" id="uf3fd87b6" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="uae2317f5" id="uae2317f5"><span data-lake-id="u7e4ff949" id="u7e4ff949" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">在这个链表中，我们想要查找一个数，需要从头结点开始向后依次遍历和匹配，直到查到为止，这个过程是比较耗费时间的，他的时间复杂度是0（n）。</span></p>
  <p data-lake-id="uba1b582e" id="uba1b582e"><span data-lake-id="u74c2f733" id="u74c2f733" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="uba7bc74d" id="uba7bc74d"><span data-lake-id="u646ec1b2" id="u646ec1b2" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">当我们想要向这个链表中插入一个数的时候，过程和查找类似，先需要从头开始遍历找到合适的为止，然后再插入，他的时间复杂度也是 O(n)。</span></p>
  <p data-lake-id="u8f9f90d2" id="u8f9f90d2"><span data-lake-id="ufc65e776" id="ufc65e776" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u81f99a18" id="u81f99a18"><span data-lake-id="ud5f94444" id="ud5f94444" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">那么，怎么能提升遍历速度呢，有一个办法，那就是我们对链表进行改造，先对链表中每两个节点建立第一级索引，如下图所示：</span></p>
  <p data-lake-id="u18b92bbf" id="u18b92bbf"><span data-lake-id="u7b02edb0" id="u7b02edb0" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u98b8248f" id="u98b8248f"><img src="https://cdn.nlark.com/yuque/0/2022/png/5378072/1671868119609-f901bb87-1a52-4aee-b5ac-bbc9ebc04e80.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_38%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="uefa155c3" id="uefa155c3"><span data-lake-id="u461db59a" id="u461db59a" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u8492b109" id="u8492b109"><span data-lake-id="uf6fd3d78" id="uf6fd3d78" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">有了我们创建的这个索引之后，我们查询元素12，我们先从一级索引6 -&gt; 9 -&gt; 17 -&gt; 26中查找，发现12介于9和17之间，然后，转移到下一层进行搜索，即9 -&gt; 12 -&gt; 17，即可找到12这个节点了。</span></p>
  <p data-lake-id="ua1738b32" id="ua1738b32"><span data-lake-id="u09d5a482" id="u09d5a482" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u10a0aa03" id="u10a0aa03"><span data-lake-id="u1521961a" id="u1521961a" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">可以看到，同样是查找12，原来的链表需要遍历5个元素(3、6、7、9、12)，建立了一层索引之后，只需要遍历4个元素即可（6、9、17、12）。</span></p>
  <p data-lake-id="u6cbc7dd5" id="u6cbc7dd5"><span data-lake-id="u4980faa2" id="u4980faa2" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u538e71b4" id="u538e71b4"><span data-lake-id="ua4fc6a18" id="ua4fc6a18" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">有了上面的经验，我们可以继续创建二级索引、三级索引....</span></p>
  <p data-lake-id="u084e626e" id="u084e626e"><span data-lake-id="u8a3f84f7" id="u8a3f84f7" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u840a0d54" id="u840a0d54"><img src="https://cdn.nlark.com/yuque/0/2022/png/5378072/1671868142391-2305b965-e436-49e2-bdc8-8ae25019001a.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_38%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ufaa826aa" id="ufaa826aa"><br></p>
  <p data-lake-id="ub5a7d83a" id="ub5a7d83a"><span data-lake-id="u2d76847b" id="u2d76847b" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">在这样一个链表中查找12这个元素，只需要遍历2个节点就可以了（9、12）。</span></p>
  <p data-lake-id="u60826872" id="u60826872"><span data-lake-id="uf12bc29a" id="uf12bc29a" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u27511486" id="u27511486"><span data-lake-id="ue1fe5b40" id="ue1fe5b40" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">因为我们的链表不够大，查找的元素也比较靠前，所以速度上的感知可能没那么大，但是如果是在成千上万个节点、甚至数十万、百万个节点中遍历呢？这样的数据结构就能大大提高效率。</span></p>
  <p data-lake-id="ud61ed9b8" id="ud61ed9b8"><span data-lake-id="ue0461a91" id="ue0461a91" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u12af8740" id="u12af8740"><span data-lake-id="u9406f163" id="u9406f163" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">像上面这种带多级索引的链表，就是跳表。</span></p>
 </body>
</html>